#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include <cuda_runtime.h>
#include <cublas_v2.h>


typedef float elemType;

int parallel = 1000;
int automatonSize = 9;
int alphabetSize = 128;
int matrixNum = 9;
int matrixSize = automatonSize * alphabetSize;
int maxMul = parallel * automatonSize;


struct Task {
    char* str;
    int len;
    int pos;
    int matched;
    elemType* vector;
};

struct Queue {
    Task* queue;
    int l, r;
    int size;
};



Queue queue;


void createQueue(int size) {
    queue.size = size;
    queue.l = queue.r = 0;
    queue.queue = (Task*)malloc(size * sizeof(Task));
}


void newTask(char* s, elemType* vector) {
    queue.queue[queue.r].str = s;
    queue.queue[queue.r].len = strlen(s);
    queue.queue[queue.r].pos = 0;
    queue.queue[queue.r].matched = 0;
    queue.queue[queue.r].vector = vector;
    vector[0] = 1;
    queue.r = (queue.r + 1) % queue.size;
}


char tmp[1000];
int readLine() {
    char c;
    int k = 0;
    while ((c=getchar()) != '\n' && c != EOF) {
        tmp[k++] = c;
    }

    if (k != 0) {
        return k;
    } else if (c != EOF) {
        return readLine();
    } else {
        return -1;
    }
}


void set(elemType* m, elemType val, int i, int j) {
    m[i * alphabetSize + j] = val;
}

void fillMatrices(elemType** m) {
    for (int i = '0'; i <= '9'; i++) {
        set(m[0], 1, 1, i);
        set(m[1], 1, 2, i);
        set(m[3], 1, 4, i);
        set(m[4], 1, 5, i);
        set(m[6], 1, 7, i);
        set(m[7], 1, 8, i);
    }
    set(m[1], 1, 3, '/');
    set(m[2], 1, 2, '/');
    set(m[4], 1, 6, '/');
    set(m[5], 1, 6, '/');
}

char* input[1500000];
int main(int argc, char** argv)
{    

    freopen("c:/Users/Sergey/Downloads/howto/howto", "r", stdin);
	int inputLen = 0;
	for (int i = 0; readLine() != -1; i++, inputLen++) {
		int len = strlen(tmp);
        input[i] = (char*)malloc(len * sizeof(char) + 1);
        for (int j = 0; j <= len; j++) {
            input[i][j] = tmp[j];
        }
	}

    
    cublasStatus_t status;
    cublasHandle_t handle;

    status = cublasCreate(&handle);
    if (status != CUBLAS_STATUS_SUCCESS) {
        fprintf (stderr, "!!!! CUBLAS initialization error\n");
        return EXIT_FAILURE;
    }


	


	elemType** hostMatrices = (elemType**)malloc(matrixNum * sizeof(elemType*));
	for (int i = 0; i < matrixNum; i++) {
		hostMatrices[i] = (elemType*)malloc(matrixSize * sizeof(elemType));
	}
   fillMatrices(hostMatrices); // TODO

	elemType** deviceMatrices = (elemType**)malloc(matrixNum * sizeof(elemType*));
	for (int i = 0; i < matrixNum; i++) {
		cudaMalloc((void**)(&deviceMatrices[i]), matrixSize * sizeof(elemType));
	}

	for (int i = 0; i < matrixNum; i++) {
		cublasSetVector(matrixSize, sizeof(elemType), hostMatrices[i], 1, deviceMatrices[i], 1);
	}

	elemType** hostMatricesPointers = (elemType**)malloc(maxMul * sizeof(elemType*));
	elemType** deviceMatricesPointers = NULL;
	cudaMalloc((void**)&deviceMatricesPointers, maxMul * sizeof(elemType*));


	elemType** hostVectorsPointers = (elemType**)malloc(maxMul * sizeof(elemType*));
	elemType** deviceVectorsPointers = NULL;
	cudaMalloc((void**)&deviceVectorsPointers, maxMul * sizeof(elemType*));

    elemType** hostInputVectors = (elemType**)malloc(alphabetSize * sizeof(elemType*));
    for (int i = 0; i < alphabetSize; i++) {
        hostInputVectors[i] = (elemType*)malloc(alphabetSize * sizeof(elemType));
        for (int j = 0; j < alphabetSize; j++) {
            hostInputVectors[i][j] = 0;
        }
        hostInputVectors[i][i] = 1;
    }

    elemType** deviceInputVectors = NULL;
    cudaMalloc((void**)&deviceInputVectors, alphabetSize * sizeof(elemType*));
    for (int i = 0; i < alphabetSize; i++) {
        cudaMalloc((void**)(&deviceInputVectors[i]), alphabetSize * sizeof(elemType));
    }

    for (int i = 0; i < alphabetSize; i++) {
        cublasSetVector(alphabetSize, sizeof(elemType), hostInputVectors[i], 1, deviceInputVectors[i], 1);
    }

    elemType** hostInputVectorsPointers = (elemType**)malloc(maxMul * sizeof(elemType*));
    elemType** deviceInputVectorsPointers = NULL;
    cudaMalloc((void**)&deviceInputVectorsPointers, maxMul * sizeof(elemType*));    


	elemType** hostResultVectors = (elemType**)malloc(maxMul * sizeof(elemType*));
    for (int i = 0; i < alphabetSize; i++) {
        hostResultVectors[i] = (elemType*)malloc(matrixNum * sizeof(elemType));
    }
	elemType** deviceResultVectors = NULL;
	cudaMalloc((void**)&deviceResultVectors, maxMul * sizeof(elemType*));
	for (int i = 0; i < matrixNum; i++) {
		cudaMalloc((void**)&deviceResultVectors[i], matrixNum * sizeof(elemType));
	}


	int* finalStates = (int*)malloc(automatonSize * sizeof(int));
    finalStates[8] = 1;


    elemType alpha = 1.0;
    elemType beta = 0.0;
    elemType* tmpVector = (elemType*)malloc(automatonSize * sizeof(elemType));
    int matched = 0;
    createQueue(parallel);

	int beginTime = clock();
	int lines = 0;
    do {
        while ((queue.r + queue.size - queue.l) % queue.size < parallel && lines < inputLen) {
            elemType* v = (elemType*)malloc(automatonSize * sizeof(elemType));
            newTask(input[lines], v);

			lines++;
			//65536, 16384, 4096
			if (lines == 4096 || lines == 16384 || lines == 65536 || lines == 100000 || lines == 500000 || lines == 700000) {
				printf("%d %d\n", lines, clock() - beginTime);
			}
        }
      
		int muls = 0;
        for (int i = queue.l; i != queue.r; i = (i + 1) % queue.size) {
            Task *t = &queue.queue[i];
            for (int j = 0; j < automatonSize; j++) {
                if (t->vector[j] == 1) {
                    hostMatricesPointers[muls] = deviceMatrices[j];
                    hostInputVectorsPointers[muls] = deviceInputVectors[t->str[t->pos]];
                    muls++;
                }
            }
        }

        cublasSetVector(muls, sizeof(elemType), hostMatricesPointers, 1, deviceMatricesPointers, 1);
        cublasSetVector(muls, sizeof(elemType), hostInputVectorsPointers, 1, deviceInputVectorsPointers, 1);

        for (int i = 0; i < muls; i++) {
            cublasSgemm(handle, CUBLAS_OP_N, CUBLAS_OP_N, automatonSize, 1, alphabetSize, &alpha,
                hostMatricesPointers[i], automatonSize, hostInputVectorsPointers[i], alphabetSize, &beta, deviceResultVectors[i], automatonSize);
        }
        for (int i = 0; i < muls; i++) {
            cublasGetVector(automatonSize, sizeof(elemType), deviceResultVectors[i], 1, hostResultVectors[i], 1);
        }

  
        int prevR = queue.r;
        for (int i = queue.l; i != prevR; i = (i + 1) % queue.size) {
            Task *t = &queue.queue[i];
            for (int j = 0; j < automatonSize; j++) {
                tmpVector[j] = 0;
            }
            muls = 0;
            for (int j = 0; j < automatonSize; j++) {
                if (t->vector[j] == 1) {
                    for (int k = 0; k < automatonSize; k++) {
                        tmpVector[k] += hostResultVectors[muls][k];
                    }
                    muls++;
                }
            }

            for (int j = 0; j < automatonSize; j++) {
                if (tmpVector[j] == 0) {
                    t->vector[j] = 0;
                } else {
                    t->vector[j] = 1;
                }
            }

            int isMatched = 0;
            for (int j = 0; j < automatonSize; j++) {
                if (finalStates[j] == 1 && t->vector[j] == 1) {
                    isMatched = 1;
                }
            }

			if (!isMatched && t->pos < t->len - 1) {
                queue.queue[queue.r] = *t;
                t->pos++;
                queue.r = (queue.r + 1) % queue.size;
            }
        }
		queue.l = prevR;
    } while (queue.l != queue.r);

	

    for (int i = 0; i < matrixNum; i++) {
        free(hostMatrices[i]);
    }
    free(hostMatrices);

    for (int i = 0; i < matrixNum; i++) {
        cudaFree(deviceMatrices[i]);
    }
    cudaFree(deviceMatrices);

    free(hostMatricesPointers);
    cudaFree(deviceMatricesPointers);


    free(hostVectorsPointers);
    cudaFree(deviceVectorsPointers);

    for (int i = 0; i < alphabetSize; i++) {
        free(hostInputVectors[i]);
    }
    free(hostInputVectors);

    for (int i = 0; i < alphabetSize; i++) {
        cudaFree(deviceInputVectors[i]);
    }
    cudaFree(deviceInputVectors);

    free(hostInputVectorsPointers);
    cudaFree(deviceInputVectorsPointers);


    for (int i = 0; i < alphabetSize; i++) {
        free(hostResultVectors[i]);
    }
    free(hostResultVectors);

    for (int i = 0; i < matrixNum; i++) {
        cudaFree(deviceResultVectors[i]);
    }
    cudaFree(deviceResultVectors);


    free(finalStates);
    free(tmpVector);


    status = cublasDestroy(handle);
    if (status != CUBLAS_STATUS_SUCCESS) {
        return EXIT_FAILURE;
    }

    int endTime = clock();
    printf("time = %d\n", endTime - beginTime);
    return EXIT_SUCCESS;
}
